#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#define HashLength 1000

typedef enum
  {
    NONE,
    DEFINE,
    START,
    VARIABLES,
    DIGIT,
    STRING,
    LEFTCBRACKET, //[
    RIGHTCBRACKET,//]
    LEFTSBRACKET ,//{
    RIGHTSBRACKET,//}
    INCLUDE ,
    DOT,          //.
    GREAT,        //>
    LESS,         //<
    NUMBER,
    IDENTITY,
    STAR,         //*
    SEMICOLON,    //,
    LEFTPARENTHESIS,      //(
    RIGHTPARENTHESIS,     //)
    LEFTQUOTE,    //'
    SHARP,        //#
    COLON,        //:
    UNDERSCORE,   //_
    SPACE,        //
    ENTERLINE,    //\n
    TAB,          //\t
    PLUS,         // +
    MINUS,        // -
    DIV,          ///
    ASSIGN,        // =
    EQUAL,       // ==  
    QMARK,        //?
    SLASH,        
    VBAR,          //|
    DOLLAR,       //$
    POW,          //^
    AT,           //@
    TILDE,        //~
    AUTO,
    BREAK,
    CASE,
    CHAR,
    CONST,
    CONTINUE,
    DEFAULT,
    DO,
    DOUBLE,
    ELSE,
    ENUM,
    EXTERN,
    FLOAT,
    FOR,
    GOTO,
    IF,
    INLINE,
    INT,
    LONG,
    REGISTER,
    RESTRICT,
    RETURN,
    SHORT,
    SIGNED,
    SIZEOF,
    STATIC,
    STRUCT,
    SWITCH,
    TYPEDEF,
    UNION,
    UNSIGNED,
    VOID,
    VOLATILE,
    WHILE 
  }TreeType;



struct map
{
  char *name;
  TreeType t;
};

struct map xmap[] = {
  {"typedef",TYPEDEF},
  {"include",INCLUDE},
  {"auto",AUTO},
  {"break",BREAK},
  {"case",CASE},
  {"char",CHAR},
  {"const",CONST},
  {"continue",CONTINUE},
  {"default",DEFAULT},
  {"do",DO},
  {"double",DOUBLE},
  {"else",ELSE},
  {"enum",ENUM},
  {"extern",EXTERN},
  {"float",FLOAT},
  {"for",FOR},
  {"goto",GOTO},
  {"if",IF},
  {"inline",INLINE},
  {"int",INT},
  {"long",LONG},
  {"register",REGISTER},
  {"restrict",RESTRICT},
  {"return",RETURN},
  {"short",SHORT},
  {"signed",SIGNED},
  {"sizeof",SIZEOF},
  {"static",STATIC},
  {"struct",STRUCT},
  {"switch",SWITCH},
  {"typedef",TYPEDEF},
  {"union",UNION},
  {"unsigned",UNSIGNED},
  {"void",VOID},
  {"volatile",VOLATILE},
  {"while ",WHILE },
  {"[",    LEFTCBRACKET},
  {"]",    RIGHTCBRACKET},
  {"{",    LEFTSBRACKET },
  {"}",    RIGHTSBRACKET},
  {".",    DOT},
  {">",    GREAT},
  {"<",    LESS},
  {"*",    STAR},
  {",",    SEMICOLON},
  {"(",    LEFTPARENTHESIS},
  {")",    RIGHTPARENTHESIS},
  {"'",    LEFTQUOTE},
  {"#",    SHARP},
  {":",    COLON},
  {"_",    UNDERSCORE},
  {" ",    SPACE},
  {"\n",    ENTERLINE},
  {"\t",    TAB},
  {"+",    PLUS},
  {"-",    MINUS},
  {"",    DIV},
  {"=",    ASSIGN},
  {"==",   EQUAL},  
  {"?",    QMARK},
  {"\\",    SLASH},
  {"|",    VBAR},
  {"$",    DOLLAR},
  {"^",    POW},
  {"@",    AT},
  {"~",    TILDE}
};

typedef struct hashbucket
{
  char name[40];
  TreeType t;
  struct hashbucket *next;
  struct hashbucket *startNode; 
}HashBucket;

typedef struct hashtable
{
  char *tableName;
  HashBucket buckets[100000];
}HashTable;

int xstrcmp(char *p1,char *p2)
{
  char *pt1 = p1;
  char *pt2 = p2;
  while(*pt1 != '\0'&& *pt2 != '\0')
    {
      if(*pt1 > *pt2)
        return 1;
      else if(*pt1<*pt2)
        return -1;

      pt1++;
      pt2++;
    }

  if(*pt1 == '\0'&& *pt2 == '\0')  
    {
      return 0;
    }

  if(*pt1 == '\0') 
    return  -1;
  else if(*pt2 == '\0') 
    return 1;

  return 1;
}

/*
  hash(abcd..e) = (a^2 + b^2 + ... + e^2)%HashLength;
 */

int HashString_test(char *p)
{
	char *s = p;
	int hashValue=0;
	while(*s!='\0')
	{
		hashValue += ((int)(*s))*((int)(*s));
		if(hashValue>HashLength)
			hashValue = hashValue%HashLength;
		s++;
	}
	return hashValue;
}


HashTable table;

/*
  
 */
TreeType StringType(char *newToken)
{
  if(xstrcmp(newToken,"Typedef") == 0) 
    {
      return TYPEDEF;
    }
  else if(xstrcmp(newToken,"include") == 0) 
    {
      return INCLUDE;
    }
  return NONE;
}

TreeType CharType(char p)
{
  return NONE;
}

/*
  
 */
void install(char *newToken)
{
  int index = HashString_test(newToken);

  HashBucket *tBucket = (HashBucket *)malloc(sizeof(HashBucket));

  strcpy(tBucket -> name ,newToken);
  
  if(table.buckets[index].next == NULL)
    {
      table.buckets[index].next = tBucket;
      tBucket -> startNode = &(table.buckets[index]); 
    }
  else
    {
      tBucket -> startNode = &(table.buckets[index]);
      tBucket -> next = table.buckets[index].next;
      table.buckets[index].next = tBucket;
    }
}


//if lookup is existed, return 0;
//if it is no existed,return 1;
int lookup(char *p)
{
  int index = HashString_test(p);
  HashBucket *begin;

  if(table.buckets[index].next != NULL)
    {
      begin = table.buckets[index].next;
    }

  for(;begin!= NULL;begin = begin -> next)  
    {
      if(strcmp(p,begin -> name) == 0)  
        {
          return 0;
        }
    }

  return 1;
}


#if 0
#define HashTableTestMain main
#endif

int HashTableTestMain(int argc,char **argv)
{
	char *t1 = "typedef";
	char *t2 = "unsigned";
	char *t3 = "long";
	char *t4 = "u_long";

        printf("%d\n",sizeof(xmap)/sizeof(xmap[0]));

        //        Token *newToken = (Token *)malloc(sizeof(Token));

        //        memset(newToken,0,sizeof(Token));

        //        strcpy(newToken -> name,t1);
        //        newToken -> t = TYPEDEF;
        
        install(t1);

        if(lookup(t1) == 0)  
          {
            printf("install typedef token successfully!!!!!\n");
          }

        install(t2);

        if(lookup(t2) == 0)  
          {
            printf("install t2 token successfully!!!!!\n");
          }

        install(t3);

        if(lookup(t3) == 0)  
          {
            printf("install t3 token successfully!!!!!\n");
          }

        if(lookup(t4) == 0)  
          {
            printf("install t4 token successfully!!!!!\n");
          }
	return 0;
}
